Some embodiments described herein relate generally to switch fabric systems, and, in particular, to methods and apparatus for randomly distributing traffic within a multi-path switch fabric system.
Some known switch fabric systems use a round-robin algorithm (RR) to distribute traffic over available data paths, where a round-robin pointer is used to select an egress port from a list of egress ports in a switch device for sending a data item. Alternatively, a deficit-weighted round-robin algorithm (DWRR) is used in other embodiments where each egress port and/or each data item is associated with a weighted credit. To implement RR or DWRR, destination devices are usually grouped, with each group maintaining its own RR or DWRR state consisting of a set of available egress ports and a round-robin pointer. Because each group maintains its own round-robin pointer, however, several groups' pointers can possibly become aligned and advance in lock-step, as long as a particular traffic pattern repeats. This leads to instantaneous queue build-up at a single egress port within a switch device. Furthermore, even if only a single group is present per switch device, the fact that multiple switch devices are at one stage of a switch fabric can produce lock-stepped pointers in a similar way, which can lead to queue build-up in the immediately following stage.
Accordingly, a need exists for a path-selection algorithm that can prevent correlated behavior such as lock-stepped pointers within, and across switch devices, in a multi-path switch fabric system.